package com.nuo.laboratory.dataStructure.tree;

import java.util.*;

/**
 * 前置排序 中左右
 * 中置排序 左中右
 * 尾置排序 左右中 == （中右左的反序  和前置排序类型）
 * 都属于DFS深度优先搜索
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * DSF 前置排序-利用队列 中左右
     * 利用队列的先进先出特性
     */
    public List<Integer> preOrder1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            result.add(poll.val);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        return result;
    }


    /**
     * DSF 前置排序-利用栈 中左右
     * 利用栈的后入先出特性
     */
    public List<Integer> preOrder2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode peek = stack.pop();
            if (peek != null) {
                // 中
                result.add(peek.val);
                // 右
                if (peek.right != null) {
                    stack.push(peek.right);
                }
                // 左
                if (peek.left != null) {
                    stack.push(peek.left);
                }
            }
        }
        return result;
    }

    /**
     * DSF 中置排序-利用栈 左中右
     * 利用栈的后入先出特性
     */
    public List<Integer> middleOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 先把所有左边放入栈中
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 先输出最左边数据 再次循环
            if (!stack.isEmpty()) {
                root = stack.pop();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }


    /**
     * DSF 尾置排序-利用栈 左右中
     * 利用栈的后入先出特性
     * 尾置排序 左右中 == （中右左的反序 和前置排序类似）
     */
    public List<Integer> endOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop != null) {
                result.add(pop.val);
                if (pop.left != null) {
                    stack.push(pop.left);
                }
                if (pop.right != null) {
                    stack.push(pop.right);
                }
            }
        }
        Collections.reverse(result);
        return result;
    }


    /**
     * BSF 利用队列 二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode peek = queue.poll();
                if (peek != null) {
                    levelList.add(peek.val);
                    if (peek.left != null) {
                        queue.offer(peek.left);
                    }
                    if (peek.right != null) {
                        queue.offer(peek.right);
                    }
                }
            }
            result.add(levelList);
        }
        return result;
    }

    /**
     * BSF 递归 二叉树的层序遍历
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        order(result, root, 0);
        return result;
    }

    private void order(List<List<Integer>> list, TreeNode node, int level) {
        if (node == null) {
            return;
        }
        if (list.size() <= level) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(node.val);
        order(list, node.left, level + 1);
        order(list, node.right, level + 1);
    }

    /**
     * 是否是对称二叉树
     * 两个节点同时为空true，两个节点其中一个为空false
     * 两个节点相等 且 左节点的左子树等于有节点的右子树 且 左节点的右子树等于右节点的左子树，为镜像返回true。
     */
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        return (t1.val == t2.val)
                && isMirror(t1.left, t2.right)
                && isMirror(t1.right, t2.left);
    }


    /**
     * 最小深度
     */
    public int getMinDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getMinDepth(root.left) + 1;
        int rightDepth = getMinDepth(root.right) + 1;
        return Math.min(leftDepth, rightDepth);
    }

    /**
     * 二叉树最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 路径总和
     * 最后一个值一定等于剩余值
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

}


